package Top200;

import common.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-27 15:27
 * 递归
 * 1、遍历n个不同的root
 * 2、递归构造左右子树
 * 3、为每个root节点遍历所有的左右子树
 */
public class generateTrees95 {

    List<TreeNode> build(int left,int right){
        List<TreeNode> res=new LinkedList<>();
        if (left>right){
            res.add(null);
            return res;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftNode = build(left, i-1);
            List<TreeNode> rightNode = build(i + 1, right);
            for (TreeNode le:leftNode) {
                for (TreeNode ri:rightNode) {
                    TreeNode root=new TreeNode(i);
                    root.left=le;
                    root.right=ri;
                    res.add(root);
                }
            }
        }
        return res;
    }
    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }
}
